package com.dorozco.trains.model;

import java.util.ArrayList;
import java.util.List;

import exceptions.NoPathBetweenStationsException;

public class TrainsMap {

	private Station[] stations;

	private int[][] paths;

	private int qtyStations;

	private final int infiniteDistance = 999999;
	
	public TrainsMap(int stationsQty, Station[] stations, List<Path> stationsPaths) {
		this.stations = new Station[stationsQty];
		this.paths = new int[stationsQty][stationsQty];
		this.qtyStations = stationsQty;

		for (int j = 0; j < stationsQty; j++) {
			for (int i = 0; i < stationsQty; i++) {
				paths[i][j] = -1;
			}
		}
		
		this.setStations(stations);
		for (Path path : stationsPaths) {
			this.addPath(path.getStationFrom().getId(), path.getStationTo().getId(), path.getCost());
		}
	}

	/**
	 * Calculate distance between first and last stations, stopping in each stations of the array
	 * @param stations array composed of consecutive stations
	 * @return Distance between first and last stations
	 * @throws NoPathBetweenStationsException If there is no path between two consecutive stations
	 */
	public int distanceBetween(Station[] stations) throws NoPathBetweenStationsException {
		int distance = 0;
		for(int i = 1; i < stations.length; i++) {
			int stationFromId = stations[i-1].getId();
			int stationToId = stations[i].getId();
			if (this.existDirectPath(stationFromId, stationToId)) {
				distance += paths[stationFromId][stationToId];
			} else {
				throw new NoPathBetweenStationsException();
			}
		}
		
		return distance;
	}
	
	/**
	 * Calculate quantity of paths between two stations, no necessary consecutive, that has a limit quantity of stops.
	 * @param stationFrom station where it starts
	 * @param stationTo station where it ends
	 * @param limit maximum quantity of stations where it stops. First station is not considered a stop, but last one is considered.
	 * @return quantity of paths found with maximum quantity of stops
	 */
	public int qtyPatshWithLimitStops(Station stationFrom, Station stationTo, int limit) {
		return this.qtyPathsWithLimitStops(stationFrom.getId(), stationTo.getId(), limit, 0, false);
	}
	
	/**
	 * Calculate quantity of paths between two stations, no necessary consecutive, that has exactly a quantity of stops
	 * @param stationFrom station where it starts
	 * @param stationTo station where it ends
	 * @param limit quantity of stops the complete path has. First station is not considered a stop, but last one is considered. 
	 * @return quantity of paths found with exactly quantity of stops.
	 */
	public int qtyPathsWithExactlyStops(Station stationFrom, Station stationTo, int limit) {
		return this.qtyPathsWithLimitStops(stationFrom.getId(), stationTo.getId(), limit, 0, true);
	}
	
	/**
	 * Calculate quantity of paths between two stations, no necessary consecutive, that has a limit distance to travel.
	 * @param stationFrom station where it starts
	 * @param stationTo station where it ends
	 * @param limitDistance limit distance to travel.
	 * @return quantity of paths found with a limit distance traveled.
	 */
	public int qtyPathsWithLimitDistance(Station stationFrom, Station stationTo, int limitDistance) {
		return this.qtyPathsWithLimitDistance(stationFrom.getId(), stationTo.getId(), limitDistance, 0);
	}
	
	/**
	 * Calculate shortest distance between two stations.
	 * @param stationFrom station where it starts
	 * @param stationTo station where it ends
	 * @return shortest possible distance traveled between two stations
	 */
	public int shortestDistanceBetween(Station stationFrom, Station stationTo) {
		return this.shortestDistance(stationFrom)[stationTo.getId()];
	}
	
	/**
	 * Calculate shortest distance between start station and all the stations, including start station too.
	 * @param stationFrom station where it starts
	 * @return an array representing shortest possible distance traveled between start stations and all the stations.
	 */
	public int[] shortestDistance(Station stationFrom) {
		boolean isInFirstStep = true;
		List<Integer> nextStations = new ArrayList<Integer>();
		int distances[] = new int[qtyStations];
		boolean visited[] = new boolean[qtyStations];
		List<Station> stationsList = new ArrayList<Station>();
		int previousStations[] = new int[999999];
		
		for(int i = 0 ; i < qtyStations ; ++i) {
			distances[i] = infiniteDistance;
			visited[i] = false;
			previousStations[i] = -1;
		}
		
		stationsList.add(stationFrom);
		distances[stationFrom.getId()] = 0;
	    int currentStationId = stationFrom.getId(), nextStationId, pathDistance;
	    while(!stationsList.isEmpty()) {
	        currentStationId = this.getClosestStation(currentStationId, stationsList);
	        stationsList.remove(getStation(currentStationId));
	        if(visited[currentStationId]) {
	        	continue;
	        }
	        
	        visited[currentStationId] = !isInFirstStep && true;
	        
	        nextStations = this.getAdjacentFromStation(currentStationId);
	        for( int i = 0 ; i < nextStations.size() ; ++i ) {
	        	nextStationId = nextStations.get(i);
	        	pathDistance = paths[currentStationId][nextStationId];
	            if(!visited[nextStationId]) {
	                if(distances[currentStationId] + pathDistance < distances[nextStationId]) {
	                	distances[nextStationId] = distances[currentStationId] + pathDistance;
	                	previousStations[nextStationId] = currentStationId;
	                	stationsList.add(this.getStation(nextStationId));
	        	    }
	            }
	        }
	        
	        if(isInFirstStep) {
	        	isInFirstStep = false;
	        	distances[stationFrom.getId()] = infiniteDistance;
	        }
	    }
	    
	    return distances;
	}
	
	public void addPath(int stationFrom, int stationTo, int cost) {
		this.paths[stationFrom][stationTo] = cost;
	}

	public Station[] getStations() {
		return stations;
	}

	public void setStations(Station[] stations) {
		this.stations = stations;
	}

	public int[][] getPaths() {
		return paths;
	}

	public void setPaths(int[][] paths) {
		this.paths = paths;
	}

	public int getQtyStations() {
		return qtyStations;
	}

	public void setQtyStations(int qtyStations) {
		this.qtyStations = qtyStations;
	}

	private boolean existDirectPath(int stationFrom, int stationTo) {
		return paths[stationFrom][stationTo] > -1;
	}
	
	private int qtyPathsWithLimitStops(int stationFrom, int stationTo, int limit, int numberStation, boolean exactlyStops) {
		if(numberStation != 0 && numberStation > limit) {
			return 0;
		} else if(numberStation != 0 && stationFrom == stationTo && (!exactlyStops || numberStation == limit)) {
			return 1;
		}
		
		List<Integer> adjacents = this.getAdjacentFromStation(stationFrom);
		int result = 0;
		for(Integer i : adjacents) {
			result += this.qtyPathsWithLimitStops(i, stationTo, limit, numberStation + 1, exactlyStops);
		}
		
		return result;
	}
	
	private int qtyPathsWithLimitDistance(int stationFrom, int stationTo, int limitDistance, int distance) {
		int qtyPaths = 0;
		if(distance != 0 && distance > limitDistance - 1) {
			return 0;
		} else if(distance != 0 && stationFrom == stationTo) {
			qtyPaths++;
		}
		
		List<Integer> adjacents = this.getAdjacentFromStation(stationFrom);
		for(Integer i : adjacents) {
			qtyPaths += this.qtyPathsWithLimitDistance(i, stationTo, limitDistance, distance + this.paths[stationFrom][i]);
		}
		
		return qtyPaths;
	}

	private List<Integer> getAdjacentFromStation(int stationId) {
		List<Integer> lista = new ArrayList<Integer>();
		for (int i = 0; i < this.qtyStations; i++) {
			if (existDirectPath(stationId, i)) {
				lista.add(i);
			}
		}

		return lista;
	}
	
	private Station getStation(int stationId) {
		for(Station s : stations) {
			if(s.getId() == stationId) {
				return s;
			}
		}
		
		return null;
	}
	
	private int getClosestStation(int currentStationId, List<Station> adjacentStations) {
		int closestStationDistance = infiniteDistance;
		int closestStationId = currentStationId;
		for(Station s : adjacentStations) {
			int distance = this.paths[currentStationId][s.getId()];
			if(closestStationDistance > distance) {
				closestStationDistance = distance;
				closestStationId = s.getId();
			}
		}
		
		return closestStationId;
	}
}
